/**
 * 
 */
package acmCoder;

import java.util.Scanner;

/**
 * @author zhongfang
 *
 */
public class 买糖果2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		while (scanner.hasNextInt()) {
			int n=scanner.nextInt();
			int v=scanner.nextInt();
			int[] p=new int[n];//魔幻银子
			int[] t=new int[n];//
			for (int i = 0; i < n; i++) {
				t[i]=scanner.nextInt();
				p[i]=scanner.nextInt();
			}
			int[][] f=new int[n][v+1];
			for (int i = t[0]; i < v+1; i++) {
				f[0][i]=p[0];
			}
			for (int i = 1; i < n; i++) {
				for (int j = v; j >= 0; j--) {
					if(v-t[i]>=0)
					f[i][j]=Math.max(f[i-1][v], f[i-1][v-t[i]]+p[i]);
					else{
						f[i][j]=f[i-1][v];
					}
				}
			}
			System.out.println(f[n-1][v]);
		}
	}

}
